1106D - Lunar New Year and a Wander - CodeForces Solution

//                                    MAY LORD BLESS YO PITTY ARSE SOUL
/*

    ███▄ ▄███▓▓█████  ██▓  ██████ ▄▄▄█████▓▓█████  ██▀███                 ▓█████▄ ▓█████  ███▄ ▄███▓
    ▓██▒▀█▀ ██▒▓█   ▀ ▓██▒▒██    ▒ ▓  ██▒ ▓▒▓█   ▀ ▓██ ▒ ██▒               ▒██▀ ██▌▓█   ▀ ▓██▒▀█▀ ██▒
    ▓██    ▓██░▒███   ▒██▒░ ▓██▄   ▒ ▓██░ ▒░▒███   ▓██ ░▄█ ▒               ░██   █▌▒███   ▓██    ▓██░
    ▒██    ▒██ ▒▓█  ▄ ░██░  ▒   ██▒░ ▓██▓ ░ ▒▓█  ▄ ▒██▀▀█▄                 ░▓█▄   ▌▒▓█  ▄ ▒██    ▒██
    ▒██▒   ░██▒░▒████▒░██░▒██████▒▒  ▒██▒ ░ ░▒████▒░██▓ ▒██▒ ██▓  ██▓  ██▓ ░▒████▓ ░▒████▒▒██▒   ░██▒
    ░ ▒░   ░  ░░░ ▒░ ░░▓  ▒ ▒▓▒ ▒ ░  ▒ ░░   ░░ ▒░ ░░ ▒▓ ░▒▓░ ▒▓▒  ▒▓▒  ▒▓▒  ▒▒▓  ▒ ░░ ▒░ ░░ ▒░   ░  ░
    ░  ░      ░ ░ ░  ░ ▒ ░░ ░▒  ░ ░    ░     ░ ░  ░  ░▒ ░ ▒░ ░▒   ░▒   ░▒   ░ ▒  ▒  ░ ░  ░░  ░      ░
    ░      ░      ░    ▒ ░░  ░  ░    ░         ░     ░░   ░  ░    ░    ░    ░ ░  ░    ░   ░      ░
        ░      ░  ░ ░        ░              ░  ░   ░       ░    ░    ░     ░       ░  ░       ░




        ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
        ⠀⠀⠀⠀⣠⣶⡾⠏⠉⠙⠳⢦⡀⠀⠀       ⠀⢠⠞⠉⠙⠲⡀⠀
        ⠀⠀⠀⣴⠿⠏⠀⠀⠀⠀⠀⠀⢳⡀⠀        ⡏⠀⠀⠀⠀⠀⢷
        ⠀⠀⢠⣟⣋⡀⢀⣀⣀⡀⠀⣀⡀⣧⠀       ⢸⠀⠀⠀⠀⠀ ⡇
        ⠀⠀⢸⣯⡭⠁⠸⣛⣟⠆⡴⣻⡲⣿⠀    .. ⣸⠀HELLO⠀⡇
        ⠀⠀⣟⣿⡭⠀⠀⠀⠀⠀⢱⠀⠀⣿⠀  .    ⢹⠀⠀⠀⠀⠀ ⡇
        ⠀⠀⠙⢿⣯⠄⠀⠀⠀⢀⡀⠀⠀⡿⠀.       ⡇⠀⠀⠀⠀⡼
        ⠀⠀⠀⠀⠹⣶⠆⠀⠀⠀⠀⠀⡴⠃⠀       ⠀⠘⠤⣄⣠⠞⠀
        ⠀⠀⠀⠀⠀⢸⣷⡦⢤⡤⢤⣞⣁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
        ⠀⠀⢀⣤⣴⣿⣏⠁⠀⠀⠸⣏⢯⣷⣖⣦⡀⠀⠀⠀⠀⠀⠀
        ⢀⣾⣽⣿⣿⣿⣿⠛⢲⣶⣾⢉⡷⣿⣿⠵⣿⠀⠀⠀⠀⠀⠀
        ⣼⣿⠍⠉⣿⡭⠉⠙⢺⣇⣼⡏⠀⠀⠀⣄⢸⠀⠀⠀⠀⠀⠀
        ⣿⣿⣧⣀⣿………⣀⣰⣏⣘⣆⣀⠀⠀
*/


#include <bits/stdc++.h>
#include <algorithm>
#pragma GCC optimize("O2")
using namespace std;

#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<long long>
#define vvl vector<vector<ll>>
#define yes "YES";
#define no "NO";
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define repe(i, a, b) for (ll i = a; i <= b; i++)
#define repi(i, a, b, k) for (ll i = a; i < b; i += k)
#define per(i, a, b) for (ll i = a; i >= b; i--)
#define input(a, n)  \
    rep(i, 0, n)     \
    {                \
        cin >> a[i]; \
    }
ll MOD = 1000000007;
// llindexL,indexR,total2;
struct DSU
{
    vector<ll> parent, sizz;
    DSU() {}
    DSU(ll n)
    {
        for (ll i = 0; i <= n; i++)
            parent.push_back(i);
        sizz.assign(n + 1, 1);
    }
    ll find_set(ll v)
    {
        if (parent[v] == v)
            return v;
        return parent[v] = find_set(parent[v]);
    }
    void union_set(ll u, ll v)
    {
        u = find_set(u);
        v = find_set(v);

        if (v == u)
            return;

        if (sizz[u] > sizz[v])
            swap(u, v);
        parent[u] = v;
        sizz[v] += sizz[u];
    }
};

void dfs(vvl &adj,priority_queue<ll,vll,greater<ll>> &pq,ll node,vll &vis,vll &pqVis)
{
    cout<<node<<" ";
    vis[node]=1;
    pq.pop();

    for(auto it: adj[node])
    {
        if(!pqVis[it]) pq.push(it);
        pqVis[it]=1;
    }

    if(!pq.empty()) dfs(adj,pq,pq.top(),vis,pqVis);
}

vector<bool> prime(1e6 + 1, true);
void SieveOfEratosthenes()
{
    for (int p = 2; p * p <= 1e6; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i <= 1e6; i += p)
                prime[i] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(9);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll tc;
    tc = 1;
    //cin >> tc;
    while (tc--)
    {
        ll n,m;
        cin>>n>>m;
        vvl adj(n+1);
        rep(i,0,m) 
        {
            ll u,v;
            cin>>u>>v;

            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        vll vis(n+1),pqVis(n+1);
        priority_queue<ll,vll,greater<ll>> pq;
        pq.push(1);
        pqVis[1]=1;
        dfs(adj,pq,1,vis,pqVis);
    }

    return 0;
}